/*
 * @lc app=leetcode.cn id=765 lang=javascript
 *
 * [765] 情侣牵手
 */

// @lc code=start
/**
 * @param {number[]} row
 * @return {number}
 */
var minSwapsCouples = function (row) {
  const size = row.length;
  const N = size >> 1;
  const graph = new Array(N).fill(0).map(() => []);

  for (let i = 0; i < size; i += 2) {
    const l = row[i] >> 1;
    const r = row[i + 1] >> 1;
    if (l !== r) {
      graph[l].push(r);
      graph[r].push(l);
    }
  }

  let result = 0;
  const visited = new Array(N).fill(false);
  for (let i = 0; i < N; i++) {
    if (!visited[i]) {
      let count = dfs(i);
      result += count - 1;
    }
  }

  return result;

  function dfs(x, count = 0) {
    visited[x] = true;
    count++;
    for (const y of graph[x]) {
      if (!visited[y]) {
        count = dfs(y, count);
      }
    }
    return count;
  }
};

// @lc code=end
